/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-04-24
 * Time:22:39
 */

/**
 * JZ26树的子结构
 */
//递归寻找
public class HasSubtree {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        return isSubStructure(root1, root2);
    }

    private boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean isSameTree(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null || A.val != B.val) {
            return false;
        }
        return isSameTree(A.left, B.left) && isSameTree(A.right, B.right);
    }






























//    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
//        if (root1 == null || root2 == null){
//            return false;
//        }
//        return isTHeHasSubTree(root1,root2);
//    }
//
//    private boolean isTHeHasSubTree(TreeNode A, TreeNode B) {
//        if (A == null || B == null){
//            return false;
//        }
//        return isSameTree(A,B) || isSameTree(A.left,B) || isSameTree(A.right,B);
//    }
//
//    private boolean isSameTree(TreeNode A, TreeNode B) {
//        if (B == null){
//            return true;
//        }
//        if (A == null || A.val != B.val){
//            return false;
//        }
//        return isSameTree(A.left, B.left) && isSameTree(A.right, B.right);
//    }

}
